package com.daaij.fourthchapter;

import java.util.Stack;

public class TreeTraverse {

    public static <T>void traverseWhileXian(TreeNode<T> head){

        TreeNode<T> tmp = head;
        Stack<TreeNode<T>> stack = new Stack<>();

        while(tmp != null) {


            //先序，由于是中左右，所以先从中往左遍历，一直到无左孩子的节点位置。
            while (tmp.left != null) {
                System.out.println(tmp);
                stack.push(tmp);
                tmp = tmp.left;
            }

            System.out.println(tmp);

            //查看是否有右孩子，如果没有，则取栈中存的之前的节点，查看他们有没有右孩子
            while (tmp.right == null && (!stack.isEmpty())) {
                tmp = stack.pop();
            }

            if (tmp.right != null) {
                tmp = tmp.right;
            } else {
                //一直找，找不到之前的节点有右孩子，说明已经遍历结束，退出
                tmp = null;
            }
        }
    }

    public static <T>void traverseWhileZhong(TreeNode<T> head){

        TreeNode<T> tmp = head;
        Stack<TreeNode<T>> stack = new Stack<>();

        while(tmp != null) {
            while (tmp.left != null) {
                stack.push(tmp);
                tmp = tmp.left;
            }


            System.out.println(tmp.value);


            while (tmp.right == null && (!stack.isEmpty())) {
                tmp = stack.pop();
                System.out.println(tmp.value);
            }

            if (tmp.right != null) {
                tmp = tmp.right;
            } else {
                tmp = null;
            }
        }

    }

    public static void traverseWhileHou(TreeNode<Integer> head){

        TreeNode<Integer> tmp = head;
        Stack<TreeNode<Integer>> stack = new Stack<>();
        Stack<TreeNode<Integer>> stack1 = new Stack<>();

        while(tmp != null) {
            while (tmp.left != null) {
                stack.push(tmp);
                tmp = tmp.left;
            }

            while (tmp.right == null && (!stack.isEmpty())) {
                System.out.println(tmp.value);
                tmp = stack.pop();

                while ((!stack1.isEmpty()) && tmp == stack1.peek()) {
                    System.out.println(tmp.value);
                    stack1.pop();
                    if(!stack.isEmpty()) {
                        tmp = stack.pop();
                    }
                }
            }


            if (tmp.right != null) {
                stack.push(tmp);
                stack1.push(tmp);
                tmp = tmp.right;
            } else {
                System.out.println(tmp.value);
                tmp = null;
            }
        }


    }


    public static void main(String[] args) {


        TreeNode<Integer> root = new TreeNode<Integer>();
        root.value = 1;

        TreeNode<Integer> num2 = new TreeNode<Integer>();
        root.left = num2;
        num2.value = 2;

        TreeNode<Integer> num3 = new TreeNode<Integer>();
        root.right = num3;
        num3.value = 3;

        TreeNode<Integer> num4 = new TreeNode<Integer>();
        num2.left = num4;
        num4.value = 4;

        TreeNode<Integer> num5 = new TreeNode<Integer>();
        num3.right = num5;
        num5.value = 5;


        //traverseWhileXian(root);
        //traverseWhileZhong(root);
        traverseWhileHou(root);


    }
}
